class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (board.size() == 0 || board[0].size() == 0) {
          return false;
        }
        int n = board.size();
        int m = board[0].size();
        vector<vector<bool> > vst(n, vector<bool>(m));

        for (int i = 0; i < n; ++i) {
          for (int j = 0; j < m; ++j) {
            if (dfs(board, word, vst, i, j, 0)) {
              return true;
            }
          }
        }
        return false;
    }

    bool dfs(const vector<vector<char> >& board, const string& word,
      vector<vector<bool> >& vst,
      int x, int y, int depth) {

      if (depth >= word.length()) {
        return true;
      }
      if (!(0 <= x && x < board.size() && 0 <= y && y < board[0].size() && !vst[x][y])) {
        return false;
      }
      if (word[depth] != board[x][y]) {
        return false;
      }
      vst[x][y] = true;
      if (dfs(board, word, vst, x + 1, y, depth + 1) ||
          dfs(board, word, vst, x - 1, y, depth + 1) ||
          dfs(board, word, vst, x, y + 1, depth + 1) ||
          dfs(board, word, vst, x, y - 1, depth + 1)) {
        return true;
      }
      vst[x][y] = false;
      return false;
    }

};
